package tree.binarytree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class BinaryTree {
    static class Node {
        int value;
        Node left;
        Node right;
        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public Node createBinaryTree() {
        Node A = new Node(1);
        Node B = new Node(2);
        Node C = new Node(3);
        Node D = new Node(4);
        Node E = new Node(5);
        Node F = new Node(6);
        Node G = new Node(7);
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        return A;
    }

    public List<Integer> preOrder(Node root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        ret.add(root.value);
        ret.addAll(preOrder(root.left));
        ret.addAll(preOrder(root.right));

        return ret;
    }

    public List<Integer> inOrder(Node root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        ret.addAll(inOrder(root.left));
        ret.add(root.value);
        ret.addAll(inOrder(root.right));

        return ret;
    }

    public List<Integer> postOrder(Node root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        ret.addAll(postOrder(root.left));
        ret.addAll(postOrder(root.right));
        ret.add(root.value);

        return ret;
    }

    public int size(Node root) {
        return root == null ? 0 : size(root.left) + size(root.right) + 1;
    }

    public int getLeafCount(Node root) {
        return root.left == null && root.right == null ? 1 : getLeafCount(root.left) + getLeafCount(root.right);
    }

    public int getKLevelCount(Node root, int k) {
        if (root == null || k < 1) return 0;
        if (k == 1) return 1;
        return getKLevelCount(root.left, k - 1) + getKLevelCount(root.right, k - 1);
    }

    public int getHeight(Node root) {
        return root == null ? 0 : Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    public Node find(Node root, int val) {
        if (root == null) return null;
        if (root.value == val) return root;
        Node left = find(root.left, val);
        if (left != null) return left;
        return find(root.right, val);
    }

    public static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Deque<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                Node cur = queue.poll();
                list.add(cur.value);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        Node root = tree.createBinaryTree();
        List<Integer> pre = tree.preOrder(root);
        List<Integer> in = tree.inOrder(root);
        List<Integer> post = tree.postOrder(root);
        System.out.println(pre);
        System.out.println(in);
        System.out.println(post);
        System.out.println(tree.size(root));
        System.out.println(tree.getLeafCount(root));
        System.out.println(tree.getHeight(root));
        System.out.println(tree.getKLevelCount(root, 2));
        System.out.println(tree.getKLevelCount(root, 3));
        System.out.println(tree.find(root, 7));
    }
}
